﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
//子集筛选2个元素以下的结果
//这个是子序列不是子集
//所有不可以提前排序


public class Solution491
{
    IList<IList<int>> res = new List<IList<int>>();
    
    public IList<IList<int>> FindSubsequences(int[] nums)
    {


        IList<int> path = new List<int>();
        
        bool[] used = new bool[nums.Length];
        res.Add(new List<int>(path));
        DFS(nums, 0, path, used);
        return res;

    }
  
    private void DFS(int[] nums, int startIndex, IList<int> path, bool[] used)
    {

        //map = new Dictionary<int, bool>();//每一层重新赋值,第一次递归就把这个引用清空了
        Dictionary<int, bool>  map = new Dictionary<int, bool>();//每一层重新实例化

        for (int i = startIndex; i < nums.Length; i++)
        {

            if (path.Count>0&&nums[i] < path[path.Count - 1])
            {
                //提前结束
                continue;
            }
            



            if (map.TryGetValue(nums[i], out bool value) && value == true)//说明用过了,但是只使用这一个flag，无法同时标注树层或者树枝
            {
                Console.WriteLine("跳过"+nums[i]);
                continue;
            }
           //这个数字没有用过才用
            

                
            map.Add(nums[i], true);
                Console.WriteLine(nums[i]);
           

          
            path.Add(nums[i]);//本次循环使用过的数字不要使用了

            if(path.Count > 1) {
                res.Add(new List<int>(path));
            }
         
          
                
            DFS(nums, i + 1, path, used);
            path.RemoveAt(path.Count - 1);

           

        }


    }
}

public class Program491
{


    static void Main491(string[] args)
    {
        Solution491 solution = new ();
        int[] nums = [1, 2, 2];
        //int[] nums = [4, 4, 3, 2, 1];
        IList<IList<int>> res = solution.FindSubsequences(nums);
        for (int i = 0; i < res.Count; i++)
        {

            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();
        }
    }

}
